﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FCA.Helper {
    public class ListHelper {
        public static void Add(List<int> list, int newValue) {
            int mid, first = 0, last = list.Count - 1;
            while (first <= last) {
                mid = (first + last) / 2;
                if (newValue < list[mid]) {
                    last = mid - 1;
                } else if (newValue > list[mid]) {
                    first = mid + 1;
                } else {
                    //don't add
                    return;
                }
            }
            list.Insert(first, newValue);            
        }

        public static bool IsSuperSet(List<int> parent, List<int> child) {
            int parentIndex = 0;
            if (child.Count == 0) return true;
            for (int i = 0; i < child.Count; i++) {
                bool isFind = false;
                for (int j = parentIndex; j < parent.Count; j++) {
                    if (parent[j] == child[i]) {
                        parentIndex = j + 1;
                        isFind = true;
                        break;
                    }
                }
                if (!isFind) {
                    return false;
                }
            }
            return true;
        }

        public static bool IsAncestorOf(List<int> ancestor, List<int> descendant) {
            return IsSuperSet(descendant, ancestor);  
        }

        public static bool IsDescendantOf(List<int> descendant, List<int> ancestor) {
            return IsSuperSet(descendant, ancestor);
        }

        public static bool IsSubSet(List<int> child, List<int> parent) {
            if (parent.Count == 0) return true;
            return IsSuperSet(parent, child);
        }

        public static bool IsEqual(List<int> list1, List<int> list2) {
            if (list1.Count != list2.Count) {
                return false;
            }
            for (int i = 0; i < list1.Count; i++) {
                if (list1[i] != list2[i]) {
                    return false;
                }
            }
            return true;
        }

        public static List<int> IntersectWith(List<int> list1, List<int> list2) {
            List<int> res = new List<int>();
            bool next = true;
            int i1 = 0;
            int i2 = 0;
            int c1 = list1.Count;
            int c2 = list2.Count;
            do {
                if (i1 >= c1 || i2 >= c2) {
                    next = false;
                } else {
                    if (list1[i1] == list2[i2]) {
                        res.Add(list1[i1]);
                        i1++;
                        i2++;
                    } else if (list1[i1] < list2[i2]) {
                        i1++;
                    } else {
                        i2++;
                    }
                }
            } while (next);
            return res;
        }

        public static List<int> UnionWith(List<int> list1, List<int> list2) {
            List<int> res = new List<int>();
            bool next = true;
            int i1 = 0;
            int i2 = 0;
            int c1 = list1.Count;
            int c2 = list2.Count;
            do {
                if (i1 >= c1 || i2 >= c2) {
                    if (i1 >= c1) {
                        //add c2 as the end of new list
                        for (int i = i2; i < c2; i++) {
                            res.Add(list2[i]);

                        }
                    } else if (i2 >= c2) {
                        for (int i = i1; i < c1; i++) {
                            res.Add(list1[i]);

                        }
                    }
                    next = false;
                } else {
                    if (list1[i1] == list2[i2]) {
                        res.Add(list1[i1]);
                        i1++;
                        i2++;

                    } else if (list1[i1] < list2[i2]) {
                        res.Add(list1[i1]);
                        i1++;
                    } else {
                        res.Add(list2[i2]);
                        i2++;
                    }
                }
            } while (next);
            return res;
        }
    }
}
